package com.test.leetcode;

class Node {
	public Node next;
	public int value;

	public Node(int value) {
		this.value = value;
	}
}

public class ListReverse {
	public static Node reverseList(Node head) {
		Node pre = null;
		Node temp = null;

		while (head != null) {
			temp = head.next;
			head.next = pre;
			pre = head;
			head = temp;
		}

		return pre;

	}

	/**
	 * 递归，在反转当前节点之前先反转后续节点
	 */
	public static Node reverseList2(Node head) {
		// head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
		if (head == null || head.next == null) {
			return head;// 若为空链或者当前结点在尾结点，则直接还回
		}
		Node reHead = reverseList2(head.next);// 先反转后续节点head.getNext()
		head.next.next = head;// 将当前结点的指针域指向前一结点
		head.next = null;// 前一结点的指针域令为null;
		return reHead;// 反转后新链表的头结点
	}

	public static void main(String[] args) {
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);

		n2.next = n3;
		n1.next = n2;

		Node n4 = reverseList2(n1);

		while (n4.next != null) {
			System.out.println(n4.value);
			n4 = n4.next;
		}
		System.out.println(n4.value);

	}

}
